1. Field of the Invention
This invention relates to methods and apparatuses for matrix reordering that is preferable for use in determination of orders of coefficient matrices of linear simultaneous equations. This invention also relates to methods and apparatuses for electronic circuit simulation using the matrix reordering.
2. Description of the Related Art
Conventionally, there are provided system simulation methods that use computers to describe elements constructing the system as linear simultaneous equations, which are repeatedly resolved to analyze operations of the system. Gaussian elimination is frequently used in the system simulation methods and is known as one of methods for obtaining solutions of the linear simultaneous equations. The Gaussian elimination produces solutions by an advance elimination process and a back-substitution process with respect to a matrix of n×n+1, which is formed by linearly arranging constant terms and coefficient matrices representing coefficients for n unknowns of linear simultaneous equations, for example. The advance elimination process is effected to transform the matrix of n×n+1 to an upper triangular matrix, while the back-substitution process is effected to sequentially produce solutions for the transformed matrix from its last row. Matrix reordering or matrix ordering is known as the technique for reordering elements (particularly, non-zero elements) of the coefficient matrices representing coefficients of the simultaneous equations in accordance with prescribed rules. Using the matrix reordering, it is possible to reduce a number of times for performing calculations such as multiplication and division that are needed for producing solutions to the linear simultaneous equations.
FIG. 14 shows a flow of processes of the conventional matrix reordering for use in the electronic circuit simulation system. In general, the conventional matrix reordering employ the prescribed method called “minimum (or least) degree method”. This is shown by a book entitled “Matrix Calculation Software” that is written and edited by Dr. Tikara Kokuni and is published by Maruzen Co., Ltd. in Japan. The flow of FIG. 14 is provided for reordering elements of a coefficient matrix of n×n. In step S101, a variable is set to ‘1’. In step S102, a pivot having a minimum degree is selected from among pivots that are not determined in order within a given coefficient matrix, then, a number of the selected pivot is set to a variable p. The coefficient matrix contains a number of pivots, wherein pivot k (where k is an integer ranging from 1 to N) designates a combination of elements of row k and elements of column k. In addition, the degree is defined as a number of non-zero elements that are contained in a plot from which elements on a diagonal line are excluded, wherein the non-zero elements counted for the degree are arranged in a lower side of the diagonal line in a column direction and in a right side of the diagonal line in a row direction. The pivot having a minimum degree is selected from among pivots whose numbers are counted from i. In step S103, new pivot i is determined by replacing its original pivot i with the selected pivot p. In step S104, non-zero elements that are produced by effecting Gaussian elimination on pivot i are added to the coefficient matrix. Replacement between pivots p and i is to interchange all elements of row p and all elements of row i and to interchange all elements of column p and all elements of column i. That is, replacement is effected simultaneously on rows and columns of pivots. A series of processes described above are repeatedly performed until all pivots are to be completely determined in order, which is shown by steps S105 and S106 in FIG. 14. According to the minimum degree method, pivots each having a small number of non-zero elements are reordered toward an upper side within the coefficient matrix. This allows reduction of a total number of calculations such as multiplication and division in the Gaussian elimination.
Using the coefficient matrix whose elements are reordered in accordance with the conventional matrix reordering method, parallel processing is executed on the Gaussian elimination process by using multiple processors in parallel. As compared with successive processing using a single processor, the parallel processing using the multiple processors does not always sufficiently increase the processing speed thereof. Because, in the Gaussian elimination process, an operational process (or calculation) for a certain row is made with reference to result of an operational process effected on another row. In the parallel processing of the Gaussian elimination process, operational processes (or calculations) are respectively made by units of rows and are performed in parallel by the multiple processors. To achieve high-speed performance of the Gaussian elimination process, it is necessary to consider several points in advance. A first point is to reduce a total number of operational processes that are effected in the parallel processing of the Gaussian elimination process. A second point is to reduce a number of operational processes that are effected on each of the rows. As for a first row, for example, its operational process is made with reference to result of an operational process of a second row, which is also made with reference to result of an operational process of a third row. Hence, it is necessary to count all of the aforementioned operational processes that are involved into the operational process being effected on each row. Although the aforementioned points are very important, the conventional matrix reordering is made in consideration of only the reduction of the total number of operational processes being effected in the Gaussian elimination process. Therefore, the conventional matrix reordering do not always contribute to high-speed performance in the parallel processing of the Gaussian elimination process.